package com.usts.edu.tree;

/**
 * Created by Guanzhong Hu
 * Date :2019/12/29
 * Description : 二叉链式存储结构
 * Version :1.0
 */
public class BiTree {

    private BiTreeNode root; // 根节点

    private static int index = 0; // 用于记录先根遍历的索引值

    public BiTree() {
        this.root = null; // 初始化，根节点为空
    }

    public BiTree(BiTreeNode root) {
        this.root = root; // 生成第一棵树
    }

//    先跟遍历和中根遍历创建一颗二叉树
    public BiTree(String preOrder,String inOrder, int preIndex,int inIndex,int count){

        if (count>0){
            char r = preOrder.charAt(preIndex);
            int i = 0;
            for (;i<count;i++) {
                if (r == inOrder.charAt(i + inIndex)) break;
            }

            root = new BiTreeNode(r);
            root.lchild = new BiTree(preOrder,inOrder,preIndex+1,inIndex,i).root;
            root.rchild = new BiTree(preOrder,inOrder,preIndex+1+i,inIndex+i+1,count-i-1).root;
        }
    }

    /**
     * 遍历二叉树
     * -------------
     * 一、 先根遍历
     * 1. 访问根节点。
     * 2. 先根遍历左子树。
     * 3. 先根遍历右子树
     * 简称 中左右
     * -------------
     * 二、 中根遍历
     * 1. 中根遍历左子树
     * 2. 访问根节点
     * 3. 中根遍历右子树
     * 简称 左中右
     * -------------
     * 三、 后根遍历
     * 1. 中根遍历左子树
     * 2. 中根遍历右子树
     * 3. 访问根节点
     * 简称 左右中
     * -------------
     */
//    ==========递归执行遍历二叉树=============
//  先跟遍历 按方法一 执行
    public void preRootTraverse(BiTreeNode T){
        if (T!=null){
            System.out.println(T.data);
            preRootTraverse(T.lchild);
            preRootTraverse(T.rchild);
        }
    }
//   中跟遍历\/
    public void inRootTraverse(BiTreeNode T){
        if (T!=null){
            inRootTraverse(T.lchild);
            System.out.println(T.data);
            inRootTraverse(T.rchild);
        }
    }
//    后根遍历
    public void postRootTraverse(BiTreeNode T){
        if (T!=null){
            postRootTraverse(T.lchild);
            postRootTraverse(T.rchild);
            System.out.println(T.data);
        }
    }
//    ==========递归执行遍历二叉树=============

    public BiTreeNode getRoot(){
        return root;
    }

    public void setRoot(BiTreeNode root) {
        this.root = root;
    }
}
